package com.mj.listen2._08_动态规划;

/**
 * 最长公共子串 – 实现
 * 题目：求两个字符串的最长公共子串长度
 * ABCBA 和 BABCA 的最长公共子串是 ABC，长度为 3
 */
public class LCSubstring {
    public static void main(String[] args) {
        System.out.println(lcs("ABBA", "BABCA"));
    }

    /**
     * dp(i,j) 是以 str1[i – 1]、str2[j – 1] 结尾的最长公共子串长度：
     * dp(i,0)、dp (0,j) 初始值均为 0
     * 如果 str1[i – 1] = str2[j – 1]，那么 dp ( i , j ) = dp ( i – 1 , j – 1 ) + 1
     * 如果 str1[i – 1] ≠ str2[j – 1]，那么 dp ( i , j ) = 0
     */
    static int lcs(String str1, String str2) {
        if (str1 == null || str2 == null) return 0;
        char[] chars1 = str1.toCharArray();
        if (chars1.length == 0) return 0;
        char[] chars2 = str2.toCharArray();
        if (chars2.length == 0) return 0;

        int[][] dp = new int[chars1.length + 1][chars2.length + 1];

        int max = 0;
        for (int i = 1; i <= chars1.length; i++) {
            for (int j = 1; j <= chars2.length; j++) {
                if (chars1[i - 1] != chars2[j - 1]) continue;
                dp[i][j] = dp[i - 1][j - 1] + 1;
                max = Math.max(max, dp[i][j]);
            }
        }

        return max;
    }
}
